
#include <stdio.h>
#include <stdlib.h>


typedef double ELEM_TYPE;

// 声明顺序表类型
typedef struct
{
    ELEM_TYPE* data;  // 数据元素的首地址
    int cap;          // 总容量
    int size;         // 有效长度，即当前数据元素的个数

} vector;


// 创建一个新的顺序表
vector* create(int initial_cap)
{
    vector* v = (vector*)malloc(sizeof(vector));

    if(NULL == v)
    {
        perror("create vector fail");
        return NULL;
    }

    v->data = calloc(initial_cap, sizeof(ELEM_TYPE));

    if(NULL == v->data)
    {
        perror("create vector fail");
        free(v);
        return NULL;        
    }

    v->cap = initial_cap;
    v->size = 0;

    return v;
}


// 尾插，成功返回 0， 失败返回 1
int push_back(vector* v, ELEM_TYPE data)
{
    if(v->cap == v->size)
    {
        // 扩容，每次扩容单位为 100
        // 指定扩容单位
        const int INCREMENT_SIZE = 100;
        ELEM_TYPE* p = NULL;

        p = realloc(v->data, v->cap + INCREMENT_SIZE);

        if(NULL == p)
        {
            perror("push_back fail");
            return 1;
        }

        v->data = p;
        v->cap += INCREMENT_SIZE;
    }

    v->data[v->size] = data;
    v->size++;

    return 0;
}


// 头插，成功返回 0， 失败返回 1
int push_front(vector* v, ELEM_TYPE data)
{
    if(v->cap == v->size)
    {
        // 扩容，每次扩容单位为 100
        // 指定扩容单位
        const int INCREMENT_SIZE = 100;
        ELEM_TYPE* p = NULL;

        p = realloc(v->data, v->cap + INCREMENT_SIZE);

        if(NULL == p)
        {
            perror("push_back fail");
            return 1;
        }

        v->data = p;
        v->cap += INCREMENT_SIZE;
    }

    // 将已有元素都往后移动一个位置
    for(int i = v->size - 1; i >= 0; i--)
    {
        v->data[i + 1] = v->data[i];
    }

    // 将新元素赋给首元素
    v->data[0] = data;
    v->size++;

    return 0;
}


// 中插，成功返回 0， 失败返回 1
int insert(vector* v, unsigned int pos, ELEM_TYPE data)
{
    if(v->cap == v->size)
    {
        // 扩容，每次扩容单位为 100
        // 指定扩容单位
        const int INCREMENT_SIZE = 100;
        ELEM_TYPE* p = NULL;

        p = realloc(v->data, v->cap + INCREMENT_SIZE);

        if(NULL == p)
        {
            perror("push_back fail");
            return 1;
        }

        v->data = p;
        v->cap += INCREMENT_SIZE;
    }

    if(pos > v->size) pos = v->size;

    // 将已有元素都往后移动一个位置
    for(int i = v->size - 1; i >= pos; i--)
    {
        v->data[i + 1] = v->data[i];
    }

    // 将新元素赋给 pos 索引处的元素
    v->data[pos] = data;
    v->size++;

    return 0;
}


// 删除某个数据元素，成功返回 0， 失败返回 1
int remove_dj(vector* v, ELEM_TYPE data)
{
    int i;

    for(i = 0; i < v->size; i++)
    {
        if(v->data[i] == data) break;
    }

    if(i == v->size) return 1;

    for(; i < v->size - 1; i++)
        v->data[i] = v->data[i + 1];

    v->size--;

    // 附加优化处理，可以不用写
    if(v->cap / v->size > 2)
    {
        // 缩容
        ELEM_TYPE* p = NULL;

        p = realloc(v->data, v->cap / 2);

        if(NULL != p)
        {
            v->data = p;
            v->cap /= 2;
        }        
    }

    return 0;
}


// 修改数据元素，成功返回 0， 失败返回 1
int update(vector* v, ELEM_TYPE old_value, ELEM_TYPE new_value)
{
    int i;

    for(i = 0; i < v->size; i++)
    {
        if(v->data[i] == old_value) break;
    }

    if(i == v->size) return 1;

    v->data[i] = new_value;

    return 0;
}


// 查找某个数据元素，找到了就返回该数据元素的指针，否则返回 NULL
ELEM_TYPE* find(vector* v, ELEM_TYPE data)
{
    int i;

    for(i = 0; i < v->size; i++)
    {
        if(v->data[i] == data) break;
    }

    if(i == v->size) return NULL;

    return &(v->data[i]);   
}


// 判空
int empty(vector* v)
{
    return !(v->size);
}


// 清空
void clear(vector* v)
{
    v->size = 0;
}


// 求长度
int size(vector* v)
{
    return v->size;
}


// 快速排序算法具体实现
void quick_sort(ELEM_TYPE* data, int size)
{
    int i, j;
    ELEM_TYPE k;

    if(size <= 1) return;

    i = 0;
    j = size - 1;
    k = data[0];

    while(i != j)
    {
        while(i < j && data[j] >= k) j--;

        data[i] = data[j];

        while(i < j && data[i] <= k) i++;

        data[j] = data[i];  
    } 

    data[i] = k;

    quick_sort(data, i);
    quick_sort(data + i + 1, size - i - 1);
}


void sort(vector* v)
{
    /*
    // 采用插入排序算法实现
    int i, j;
    ELEM_TYPE tmp;

    for(i = 1; i < v->size; i++)
    {
        tmp = v->data[i];

        for(j = i - 1; j >= 0; j--)
        {
            if(v->data[j] <= tmp) break;
            v->data[j + 1] = v->data[j];
        }

        v->data[j + 1] = tmp;
    }
    */

    // 采用快速排序算法实现
    quick_sort(v->data, v->size);
}


// 遍历
void traverse(vector* v, int(*visit)(ELEM_TYPE* ))
{
    for(int i = 0; i < v->size; i++)
    {
        if(!visit(&(v->data[i]))) 
            break;
    }
}


// 销毁一个已存在的顺序表
void destroy(vector* v)
{
    free(v->data);
    free(v);
}


int show(ELEM_TYPE* data)
{
    printf("%g ", *data);
}


int main()
{
    /*
    int* a = (int*)calloc(3, sizeof(int));

    a[0] = 5;
    a[1] = 3;
    a[2] = 2;

    // 扩容
    
    // 方法一：
    // int* p = (int*)malloc(5 * sizeof(int));
    // memcpy(p, a, 3 * sizeof(int));
    // free(a);
    // a = p;

    // 方法二：
    a = realloc(a, 5 * sizeof(int));

    a[3] = 1;
    a[4] = 4;

    for(int i = 0; i < 5; i++)
    {
        printf("%d ", a[i]);
    }

    printf("\n");


    // 顺序表中删除第 2 个元素
    for(int i = 2; i < 5 - 1; i++)
    {
        a[i] = a[i + 1];
    }


    // 缩容
    a = realloc(a, 4 * sizeof(int));


    for(int i = 0; i < 4; i++)
    {
        printf("%d ", a[i]);
    }

    printf("\n");

    free(a);
    */

    vector* v1 = NULL;

    v1 = create(100);

    push_back(v1, 3.14);
    push_back(v1, 1.9);
    push_front(v1, 5.201);
    insert(v1, 1, -5.8);

    remove_dj(v1, 5.201);

    sort(v1);

    traverse(v1, show);  // -5.8 1.9 3.14
    printf("\n");

    destroy(v1);

    return 0;
}
